package com.jiang.专题.动态规划.Q96;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/08 15:15
 */
class Solution {
    // 动态规划
    // public int numTrees(int n) {
    //     int[] dp = new int[n + 1]; // dp[i] 表示节点为i时有几种不同的二叉搜索树
    //     dp[0] = 1; // 当节点为0个时，只有一种，就是null
    //     for (int i = 1; i <= n; i++) { // 计算一个节点……n个节点分别有几种不同的二叉搜索树
    //         for (int j = 1; j <= i; j++) { // 以j作为根节点， j - 1为 左子树节点个数， i - j为右子树节点个数
    //             dp[i] += dp[j - 1] * dp[i - j];
    //         }
    //     }
    //     return dp[n];
    // }

    // 数学
    public int numTrees(int n) {
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }
}
